/*
 * @lc app=leetcode.cn id=31 lang=golang
 *
 * [31] 下一个排列
 */

// @lc code=start

// 贪心--需要获取左边部分的最小值与右边部分与最小值相比最接近的较大值
// 将两者交换后，将最小值后的内容全部翻转
func nextPermutation(nums []int) {
	n := len(nums)

	a, b := -1, -1
	for i := n - 1; i > 0; i-- {
		if nums[i] <= nums[i-1] {
			continue
		} else {
			a = i - 1
			break
		}
	}
	if a >= 0 {
		for j := n - 1; j >= 0; j-- {
			if nums[j] > nums[a] {
				b = j
				break
			}
		}
		nums[a], nums[b] = nums[b], nums[a]
	}

	for i, j := a+1, n-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return
}

// @lc code=end
